The present invention relates to processing images and, in particular, to processing color images in a page description language environment. It finds particular application in conjunction with processing color images including graphical objects having at least one abutting and/or overlapping edge, and will be described with particular reference thereto. It will be appreciated, however, that the invention will also find application in processing images including text and graphical images in other arrangements, and the like.
The use of graphics in computer and communication applications is very widespread and is becoming increasingly more prevalent. A computing device often transmits a document including graphical data to a printing device using a page description language. Page description languages (e.g., the PostScript(copyright) language) include interpretive programming commands useful for implementing powerful graphics capabilities. When transmitted via a page description language, graphical data is typically first converted to a bit-map data file. Printing devices then convert the bit-map data to appropriate marks on paper.
The PostScript(copyright) page description language (xe2x80x9cPostScriptxe2x80x9d) uses what is known as a painter""s algorithm. In other words, when objects are processed using PostScript, the objects are processed in back to front order. More specifically, objects in the lowest xe2x80x9clayerxe2x80x9d of the image are processed first. Then, objects in successively higher layers are processed.
Objects, as commonly described in page description languages, generally fall into one of three classes. The most common objects are text. These are received by the rasterizer as records that contain character, font, size and placement information. These records are converted to bitmaps, which are used to mask the current color when combining them with the existing image. The bits in the mask that are xe2x80x9conxe2x80x9d correspond to pixels in the image, which are replaced with the current color; bits that are xe2x80x9coffxe2x80x9d correspond to pixels that are left unchanged. Generally speaking, text must be rasterized at a high resolution. However antialiasing (described below) makes it possible to rasterize text at a moderate resolution. Color precision is of relatively little importance in text: 16-32 shades of gray is generally sufficient.
A second type of object is commonly known as a pictorial image. Such an object is received as a collection of pixel intensity values (possibly color), along with position and transformation information. The object""s size and shape may be altered by the transformation (e.g., it may be rotated and sheared). Generally speaking, pictorial objects are acceptably rasterized by receiving and printing them at a relatively low (300 spots per inch (xe2x80x9cspixe2x80x9d) or less) resolution. Color precision, on the other hand, is relatively important for pictorials. 100-200 shades of gray (or of each of red, green and blue) is often considered a minimum for acceptable color pictorials.
The third type of object is known as synthetic graphics. Such objects are received in the form of a series of vertices describing an outline, the interior of which is to be filled with the current color. When successive synthetic graphics objects of similar colors abut, the appearance of gradual gradations may result. Alternatively, when abutting objects exhibit sharply contrasting colors, the appearance of high contrast edges may result. It is important to provide high color precision in regions of gradual gradations, while providing the appearance of high quality, high resolution at high contrast edges.
When the image is printed, the objects are arranged one on top of another on a page. An object in a higher layer will partially, or even completely, cover an object in a lower layer. Alternatively, the two (2) objects may abut one another. When printed, the edges between the overlapping or abutting objects may appear jagged. Therefore, it is often desirable to antialias these edges.
Antialiasing provides the illusion of increased resolution without incurring the costs associated with increased memory and/or increased device resolution. Processing costs are only slightly increased by antialiasing and, in some cases, are actually decreased. Costs associated with devices capable of displaying higher resolution are also avoided since antialiasing is appropriate for displaying higher-resolution data on a lower-resolution device.
The most notable improvements provided by antialiasing occur on slightly slanted lines and edges, and near the horizontal and vertical portions of gradual curves. When printed at lower resolutions without being antialiased, these features often times appear jagged. Strokes may be of any color, and edges may separate any two (2) colors. However, the most visible jagged edges are often between colors having high luminance contrast.
The tradeoffs and benefits of antialiasing depend on the resolution achievable by the final output device. Early laser printers, despite only having a capability of printing low resolution images, in many cases produced edges that appeared smooth. As xerographic technology has advanced, laser copying has become crisper, thereby producing edges that are more cleanly defined. However, one drawback to such an improvement is an increased sharpness of the edges in the image. More specifically, the sharpened edge definition makes jagged edges caused by rasterization more visible.
One approach to removing jagged edges is to increase the resolution and addressability of the output devices even further. Hence, 1,200 spot per inch printers have been developed. Depending on the contrast of the edge (which depends on the whiteness of the paper, the blackness of the ink or toner, and the illumination), the human eye perceives jaggedness up to somewhere between 1,200 and 2,400 spots per inch (at a viewing distance of about 15 cm). However, it has been shown that with gray edges, resolutions from 300 to 600 spots per inch are sufficient. In pictorial images, these lower resolutions are sufficient, provided enough levels of gray are available. Therefore, antialiasing provides a good way to represent graphical edges so that invisible information is not stored.
There are a number of known approaches to antialiasing. The simplest and best known approach is to rasterize at a higher-than-final resolution. The final image is then computed by filtering and scaling-down the high-resolution version to a low-resolution image (i.e., the final image). This method is known as supersampling. The filtering and scaling operations consist of, at each output pixel, taking an average (possibly weighted) of the pixels in the region of the high-resolution image which maps to the region of the final image surrounding that output pixel""s center.
Some advantages to this approach are that it is simple and can be implemented very rapidly on almost any system. However, this approach has at least one significant drawback over other approaches. Specifically, it may substantially increase the amount of time and memory required to antialias an image.
If the image is scaled by a factor of n (e.g., 4) (which gives n extra edge positions), nxn times as much memory is used, or at least accessed, and the processing time is substantially increased. Because memory access time (especially for large quantities of memory) has not historically decreased nearly as rapidly as processor cycle time, memory access time tends to dominate total run time. Thus, the cost of supersampling increases with resolution, in proportion to the amount of memory used.
Substantially more complex methods of antialiasing exist in which the full geometry in the region of each pixel is used to compute analytically either the weighted or unweighted average. In terms of runtime complexity, the more complex methods are better than the filtering and scaling-down method described above. Furthermore, the more complex methods theoretically give better results. However, the more complex methods are also typically more difficult to implement.
The Scitex continuous tone-line work (xe2x80x9cCT-LWxe2x80x9d) format is useful for representing pictorials. Scitex stores the CT-LW as xe2x80x9crun listsxe2x80x9d. Each run list represents data for the image in a first dimension (e.g., along an x-dimension). Multiple run lists are created to represent the data in a second dimension (e.g., along a y-dimension). The data for each run is stored as a first number identifying the color and as a second number identifying a length of the run. If it becomes desirable to antialias an image, the Scitex method performs the equivalent of nxn supersampling by increasing the precision of the run lengths (in the x-dimension) and by increasing the number of run lists (in the y-dimension). Such an approach reduces the processing cost to a factor of n over doing nothing.
Another approach to antialiasing is to use alpha-blending. In alpha-blending, only a low-resolution frame buffer is used to store the image. As each new primitive (e.g., object) is added to the frame buffer, it is immediately merged with existing data already in the frame buffer. In interior regions of an object, the merge is simply a replacement (i.e., the new data replaces the original data). In exterior regions of an object, the frame buffer is unaffected. Along an edge of an object, the fractional coverage of a pixel by the new object is computed. The color of the new object is blended with the existing color data in the frame buffer, using the computed fractional coverage, to control how much of each color is used in the antialiased pixel.
Alpha-blending is sufficient for text against a solid background, and probably for text against any background. However, it is generally not successful for abutting edges of polygons. FIG. 1 illustrates a pixel 10 of interest in a PostScript printing scheme. The pixel of interest 10 contains parts of first and second objects 12, 14, respectively, which abut each other at a common edge 16. The first object 12 is a first color and the second object 14 is a second color. The first and second colors are represented in FIG. 1 as horizontal and vertical lines, respectively.
The pixel of interest 10 shown in FIG. 1 is one of many pixels that may be used to make up a sweep or vignette. As is common in PostScript masters, the vignette is created from many abutting rectangles, of only slightly varying color.
FIG. 2 illustrates the desired antialiased final pixel 20, which would result from alpha-blending the pixel of interest illustrated in FIG. 1. The color of the desired final pixel 20 represents a blend of respective amounts, which are proportional to the fractional coverage, of the first and second colors in FIG. 1. The color of the desired final pixel 20 is represented in FIG. 2 as diagonal lines from the bottom-left to the top-right.
FIG. 3 illustrates the actual antialiased pixel 22 which would result from the pixel of interest 10 in the PostScript printing scheme shown in FIG. 1. The color of the actual pixel 22 is not consistent with the color of the desired final pixel 20 shown in FIG. 2. The color of the actual pixel 22 is represented in FIG. 3 as diagonal lines from the top-left to the bottom-right.
FIGS. 4A-4C illustrate the method by which alpha-blending is used to achieve the actual antialiased pixel 22 shown in FIG. 3. After the first object 12 is positioned on the page, the pixel of interest 10 partially covers the first object 12 and partially covers the background 24 (e.g., white). Therefore, the first object 12 is alpha-blended with the white background 24, yielding an intermediate pixel 26, which is illustrated with dashed lines in FIG. 4B. Then, the second object 14 is positioned on the page over the intermediate pixel 26 as illustrated in FIG. 4C. Alpha-blending is performed again for the intermediate pixel of interest 30. This time, the pixel of interest 30 includes the color from the second object 14 and the result from the first alpha-blending, yielding the pixel 22 shown in FIG. 3. Therefore, when alpha-blending is used with PostScript printing schemes, the actual color of the resulting pixel is a function of the colors of the objects and the background color, rather than only the colors of the objects.
The present invention provides a new and improved apparatus and method which overcomes the above-referenced problems and others.
An image, including at least two objects, is processed. All of a plurality of data for a first one of the objects is processed before any of a plurality of data for a second one of the objects is processed. To process the image, the following steps are performed for each of the data of each of the objects. Current antialiased data is received into a processing buffer. The current data is low-resolution data of a current section of the image. The current section is a part of a current object being processed. It is determined if the current section includes an edge of the current object. If the current section does not include the edge, the current low-resolution data is received into a low-resolution memory. If the current section does include the edge, it is determined if previous high-resolution data is included in a high-resolution memory. If the previous high-resolution data is included in the high-resolution memory and the previous high-resolution data corresponds to a previous section of a previously processed object having a same location within the image as the current section, the previous high-resolution data is merged with a high-resolution version of the current data. Then, the merged data is received into the high-resolution memory. If the previous high-resolution data is included in the high-resolution memory and the previous high-resolution data corresponds to a previous section of a previously processed object having a different location within the image as the current section, a low-resolution version of the previous high-resolution data from the high-resolution memory is received into the low-resolution memory. Then, original low-resolution data is received from the low-resolution memory into the processing buffer. The original low-resolution data corresponds to the same location within the image as the current section. A high-resolution version of the original low-resolution data is then merged with the high-resolution version of the current data. Lastly, the merged data is received into the high-resolution memory. If the previous high-resolution data is not included in the high-resolution memory, the high-resolution version of the current data is received in the high-resolution memory.
In accordance with one aspect of the invention, the step of receiving the current data includes identifying the current section of the current object to be processed and determining a current location identifier associated with the current section. The current location identifier identifies a position of the current section within the image.
In accordance with a more limited aspect of the invention, the step of determining if the current section includes the edge of the current object includes determining if the current low-resolution data includes a plurality of colors.
In accordance with another aspect of the invention, the step of receiving the current low-resolution data into the low-resolution memory includes determining a first memory location, within the low-resolution memory, as a function of the current location identifier and receiving the current low-resolution data into the first memory location of the low-resolution memory. The method further includes determining a second memory location, within the high-resolution memory, as a function of the current location identifier and, if the previous high-resolution data included in the second memory location corresponds to the same location within the image as the current location identifier, flagging the second memory location as invalid.
In accordance with a more limited aspect of the invention, the steps of determining the first and second memory locations includes using a hashing function.
In accordance with a more limited aspect of the invention, the step of determining if the high-resolution memory includes the previous high-resolution data includes determining if the second memory location within the high-resolution memory includes the previous high-resolution data.
In accordance with an even more limited aspect of the invention, the step of merging the previous high-resolution data with the high-resolution version of the current data includes alpha-blending the previous high-resolution data and the high-resolution version of the current data.
In accordance with another aspect of the invention, the step of receiving the merged data in the high-resolution memory includes storing the merged data in the second memory location of the high-resolution memory.
One advantage of the present invention is that the speed of antialiasing a PostScript image is increased.
Another advantage of the present invention is that the quality of antialiased PostScript images is increased.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.